package main

type BinSearchTree struct {
	Root *TreeNode
}

// NewBinSearchTree 是 BinBinTreeNode 结构体的构造函数
func NewBinSearchTree(val any) *BinSearchTree {
	return &BinSearchTree{
		Root: NewTreeNode(val),
	}
}

func (b *BinSearchTree) Search(num int) *TreeNode {
	node := b.Root
	if node == nil {
		return nil
	}

	for node != nil {
		if node.Val.(int) == num {
			return node
		}

		if node.Val.(int) > num {
			node = node.Left
		} else {
			node = node.Right
		}
	}

	return nil
}

func (b *BinSearchTree) Insert(num int) *TreeNode {
	node := b.Root
	newNode := NewTreeNode(num)
	if node == nil {
		b.Root = newNode
		return newNode
	}

	preNode := node
	for node != nil {
		if node.Val.(int) == num {
			return node
		}

		preNode = node
		if node.Val.(int) > num {
			node = node.Left
		} else {
			node = node.Right
		}
	}

	if preNode.Val.(int) > num {
		preNode.Left = newNode
	} else {
		preNode.Right = newNode
	}

	return newNode
}

func (b *BinSearchTree) Delete(num int) {
	current := b.Root
	// 如果树是空的，那么直接返回nil
	if current == nil {
		return
	}

	// 设置一个变量来保存要删除节点的父节点
	var previous *TreeNode
	for current != nil {
		// 如果找到了要删除的节点，那么结束循环，这里已经保存到了上级节点，
		// 但是上级节点还有可能是root，因为最开始node从root开始
		if current.Val.(int) == num {
			break
		}

		previous = current
		if current.Val.(int) > num {
			current = current.Left
		} else {
			current = current.Right
		}
	}

	// node是要删除的节点，如果要删除的节点为nil,说明没有找到要删除的节点，那么直接返回nil
	if current == nil {
		return
	}

	//删除节点的度为 0 或 1
	if current.Left == nil || current.Right == nil {
		var preserve *TreeNode
		if current.Left != nil {
			preserve = current.Left
		} else if current.Right != nil {
			preserve = current.Right
		}

		// 度为 0 的情况，直接删除,默认的 preserve 就是nil,所以只需要判断一下大小直接赋值即可
		if current == b.Root {
			b.Root = preserve
		} else if previous.Left == current {
			previous.Left = preserve
		} else {
			previous.Right = preserve
		}

		// 节点的度为2的情况，需要使用一个子节点替换当前要删除的节点，可以是左侧节点的最大节点，也可以是右侧节点的最小节点
	} else {
		tmp := current.Right
		for tmp.Left != nil {
			tmp = tmp.Left
		}
		b.Delete(tmp.Val.(int))
		current.Val = tmp.Val
	}
}
